class Solution
{
public:
    int findRotateSteps(string ring, string key)
    {
        int n = ring.size();
        int k = key.size();

        vector<vector<int>> charPos(26, vector<int>());
        for (int i = 0; i < n; ++i)
        {
            charPos[ring[i] - 'a'].push_back(i);
        }

        vector<vector<int>> dp(n, vector<int>(k, INT_MAX));
        for (int pos : charPos[key[0] - 'a'])
        {
            dp[pos][0] = min(pos, n - pos);
        }

        for (int i = 1; i < k; ++i)
        {
            char cur = key[i];
            char last = key[i - 1];
            for (int lastPos : charPos[last - 'a'])
            {
                for (int pos : charPos[cur - 'a'])
                {
                    int step = abs(pos - lastPos);
                    step = min(step, n - step);
                    dp[pos][i] = min(dp[pos][i], dp[lastPos][i - 1] + step);
                }
            }
        }
        int result = INT_MAX;
        for (int i = 0; i < n; ++i)
        {
            result = min(result, dp[i][k - 1]);
        }
        result += k;
        return result;
    }
};